// 模拟 时间复杂度 O(n) 空间复杂度 O(n)

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int nums[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int ret = 0;
        for (int i = 2; i <= n; i++) {
            nums[i] = nums[i / 2] + (i % 2) * nums[i / 2 + 1];
            ret = max(nums[i], ret);
        }
        return ret;
    }
};